/*
 * Saphre - Suffix Arrays for Phrase Extraction
 * Copyright (C) 2013 
 * Dale Gerdemann - Tübingen, Germany 
 * Niko Schenk - Frankfurt am Main, Germany
 * All rights reserved.
 *
 * This program is free software: you can redistribute it and/or modify it under
 * the terms of the GNU General Public License as published by the Free Software
 * Foundation, either version 3 of the License, or (at your option) any later
 * version.
 *
 * This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
 * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
 * details.
 *
 * You should have received a copy of the GNU General Public License along with
 * this program. If not, see <http://www.gnu.org/licenses/>.
 *
 */
package util.sorting;

import java.util.*;

import saphre.core.Store;

// Code adapted from original from Sedgewick/Wayne. Adapted further to
// sort prefixes instead of suffixes.
// Copyright © 2000–2011, Robert Sedgewick and Kevin Wayne.
public class RevRadixQSort {

    public static Store store;
    int[] corpus;
    int sentinel;

    public RevRadixQSort(int[] corpus) {
        this.corpus = corpus;
        this.sentinel = corpus[0];
    }

    static void exch(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    public void sort(int[] a, int lo, int hi, int d) {
        sort(a, lo, hi, d, 0);
    }

    public void sort(int[] a, int lo, int hi, int d, int r) {
        if (hi <= lo) {
            return;
        }
        int i = lo - 1, j = hi;
        int p = lo - 1, q = hi;
        int v = corpus[a[hi] - d];
        while (i < j) {

            while (corpus[a[++i] - d] < v) {
                if (i == hi) {
                    break;
                }
            }
            while (v < corpus[a[--j] - d]) {
                if (j == lo) {
                    break;
                }
            }

            if (i > j) {
                break;
            }
            exch(a, i, j);
            if (corpus[a[i] - d] == v) {
                exch(a, ++p, i);
            }
            if (corpus[a[j] - d] == v) {
                exch(a, j, --q);
            }
        }
        if (p == q) {
            if (v != sentinel) {
                sort(a, lo, hi, d + 1, r + 1);
            }
            return;
        }
        if (corpus[a[i] - d] < v) {
            i++;
        }

        for (int k = lo; k <= p; k++) {
            exch(a, k, j--);
        }

        for (int k = hi; k >= q; k--) {
            exch(a, k, i++);
        }
        sort(a, lo, j, d, r + 1);
        if ((i == hi) && (corpus[a[i] - d] == v)) {
            i++;
        }
        if (v != sentinel) {
            sort(a, j + 1, i - 1, d + 1, r + 1);
        }
        sort(a, i, hi, d, r + 1);
    }

    public static void main(String[] args) {

        int[] corN = {4, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 3};
        int n = corN.length;

        RevRadixQSort rx = new RevRadixQSort(corN);
        int[] w = new int[n];
        for (int i = 1; i < n; i++) {
            w[i] = i;
        }
        System.out.println(Arrays.toString(w));

        rx.sort(w, 1, n - 2, 0);
        System.out.println(Arrays.toString(w));
    }
}
